package cn.orange.ch08_backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * LC93.复原 IP 地址
 */
public class LC93 {
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        StringBuilder trace = new StringBuilder();
        backtracking(0, 0, s, trace, ans);
        return ans;
    }

    private void backtracking(int start, int depth, String s, StringBuilder trace, List<String> ans) {
        if (depth == 4) {
            String ip = trace.toString();
            if (ip.length() == s.length() + 4) {
                ans.add(ip.substring(0, ip.length() - 1));
            }
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String ipStr = s.substring(start, i + 1);
            if (!isValidIpStr(ipStr)) break;
            trace.append(ipStr).append(".");
            backtracking(i + 1, depth + 1, s, trace, ans);
            for (int j = 0; j <= ipStr.length(); j++) {
                trace.deleteCharAt(trace.length() - 1);
            }
        }
    }

    private boolean isValidIpStr(String ipStr) {
        if (ipStr.startsWith("0") && ipStr.length() > 1) {
            return false;
        }
        int ip = Integer.parseInt(ipStr);
        return ip >= 0 && ip <= 255;
    }

    public static void main(String[] args) {
        LC93 alg = new LC93();
        System.out.println(alg.restoreIpAddresses("25525511135"));
        System.out.println(alg.restoreIpAddresses("0000"));
        System.out.println(alg.restoreIpAddresses("101023"));
    }
}
